// https://www.lintcode.com/problem/1588/description
/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param n: An integer
     * @return: A list of root
     */
    vector<TreeNode*> allPossibleFBT(int n) {
        n--;
        vector<TreeNode*> res;
        if (!n) {
            res.push_back(new TreeNode(0));
            return res;
        }
        for (int i = 1; i < n; i += 2) {
            for (auto& left: allPossibleFBT(i)) {
                for (auto& right: allPossibleFBT(n - i)) {
                    TreeNode* root = new TreeNode(0);
                    root->left = left;
                    root->right = right;
                    res.push_back(root);
                }
            }
        }
        return res;
    }
};